package doublePointer;

import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;

public class TwoSum {
    /**
     * LeetCode T1 两数之和
     *
     * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
     *
     * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
     *
     * 你可以按任意顺序返回答案。
     *
     * 总结：对应summary.skills.Skill01 技巧六
     * @param args
     */
    public static void main(String[] args) {
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(1, 1);
        map.put(2, 1);
        Collection<Integer> values = map.values();
        for (Integer value : values) {
            System.out.println(value);
        }
    }
    /**
     * 方法一：暴力枚举，时间复杂度为n^2
     */
    public int[] twoSum(int[] nums, int target){
        int len = nums.length;
        int[] ans = new int[2];
        //设立标志位，表明查找结束，对应summary.skills.Skill01：技巧九
        boolean flag = false;
        //获得所有长度为二的组合，由于长度确定，不需要用回溯法
        for (int i = 0; i < len - 1; i++){
            for (int j = i + 1; j < len; j++){
                if (nums[i] + nums[j] == target){
                    flag = true;
                    ans[0] = i;
                    ans[1] = j;
                    break;
                }
            }
            if (flag){
                break;
            }
        }
        return ans;

    }
    /**
     * 方法二：利用hashSet的方便查找的特性，降低时间复杂度，一趟遍历即可。
     */
    public int[] twoSum2(int[] nums, int target){
        //存放结果
        //int[] ans = new int[2];
        int len = nums.length;
        HashMap<Integer, Integer> map = new HashMap<>();
        //一遍遍历得到结果
        for (int i = 0; i < len; i++){
            //判断hashmap中是否含有
            if (map.keySet().contains(target - nums[i])){
                return new int[]{map.get(target - nums[i]), i};
            }
            map.put(nums[i], i);
        }
        return new int[0];
    }
}
